package com.culture.bootdemo.controller.bitmap;

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import lombok.extern.slf4j.Slf4j;
import org.apache.lucene.util.RamUsageEstimator;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

import java.util.ArrayList;
import java.util.List;


/**
 * @author ：wen
 * @date ：Created in 2019/8/5 16:42
 * @description：: 布隆过滤器  有道笔记：
 * <p>
 * 布隆过滤器的原理：
 * 当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。
 * 检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：
 * 如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。
 * <p>
 * <p>
 * 比之BitSet的优点：
 * Bloom Filter跟单哈希函数Bit-Map(或BitSet)不同之处在于：Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概率。
 * <p>
 * <p>
 * 使用场景：
 * 1，爬虫的URL过滤。
 * 2，日志分析
 * 3，用户数统计等等等
 */
@RestController
@Slf4j
@RequestMapping("/bloomFilter")
public class BloomFilterDemo {


    private static final int size = 100_0000;
    /**
     * 布隆过滤器
     * size：过滤器的容量(预期插入的数量)
     * 默认 预期误判率为 0.03,也可自行设置
     */
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size);

    //MurmurHash、Fnv

    /**
     * 布隆过滤器使用
     */
    public void bloomFilterDemo() {
        // 初始化1000000条数据到过滤器中
        for (int i = 0; i < size; i++) {
            bloomFilter.put(i);
        }

        // 匹配已在过滤器中的值，是否有匹配不上的
        for (int i = 0; i < size; i++) {
            if (!bloomFilter.mightContain(i)) {
                System.out.println("有坏人逃脱了~~~");
            }
        }

        // 匹配不在过滤器中的10000个值，有多少匹配出来
        int count = 0;
        for (int i = size; i < size + 10000; i++) {
            if (bloomFilter.mightContain(i)) {
                count++;
            }
        }
        System.out.println("误伤的数量：" + count);
    }

    private static BloomFilter<Long> bf = BloomFilter.create(Funnels.longFunnel(), 500_0000);

    /**
     * 计算存储大小
     */
    public void testCount() {
        List<Long> list = new ArrayList<>();
        for (long i = 500_0000; i < 1000_0000; i++) {
            list.add(i);
            bf.put(i);
        }
        System.out.println("list数量：" + list.size());

        System.out.println("list在堆中大小：" + RamUsageEstimator.shallowSizeOf(list));
        System.out.println("bloomFilter在堆中大小：" + RamUsageEstimator.shallowSizeOf(bloomFilter));


        System.out.println("list在堆中大小=====：" + RamUsageEstimator.sizeOf(list));
        System.out.println("bloomFilter在堆中大小=====：" + RamUsageEstimator.sizeOf(bloomFilter));
    }


    public static void main(String[] args) {
        intTempBitMap();
    }


    /**
     * bit-map 思想将大数据量存入int数组中，判断是否存在
     */
    public static void intTempBitMap() {
        //count为这堆数的总量是多少个
        int count = 675_3214;
        //求出需要初始化的数组大小
        int init = 1 + count / 32;
        //初始化数组
        int[] array = new int[init];

        //如何将数放进去
        //1  找到对应的数组下标： word/32(或 word>>5)
        //2  求十进制数对应的bit位： word%32(或word & 0x1F)
        //3  利用移位0-31 使得对应的32bit位为1：array[word>>5] |= (1<<(word & 0x1F));  //等价于array[word/32] |= (1<<(word%32));
        int word = 151;//假设Word为需要放进数组的某一个数
        array[word >> 5] |= (1 << (word & 0x1F));

        int i = array[word >> 5] & (1 << (word & 0x1F));
//        System.out.println(JSON.toJSONString(array));
        System.out.println(i);
        System.out.println(Integer.toBinaryString(i));
        System.out.println(Integer.toBinaryString(i).length());
        System.out.println(word & 0x1F);

    }


}
